package com.kevin.learn.leetcode;

import com.alibaba.fastjson.JSON;
import com.kevin.learn.domain.Node;

import org.apache.commons.collections4.CollectionUtils;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class NodeDemo {

        public static void main(String[] args) {

            /**
             *
             *                              1
             *                           /  |  \
             *                          2   3   4
             *                        / \   /\
             *                       5  6  7  8
             *                      /     /\
             *                    11     9 10
             *                   / \
             *                 12  13
             */
            // 构建树
            Node tree = initNode();

            // 预设 命中的节点
            List<Integer> list = new ArrayList<>();
            list.add(1);
            list.add(3);
            list.add(7);
            list.add(13);

            Node node = filterTree(tree, list);
            System.out.println(JSON.toJSON(node));
            /**
             *
             *                              1
             *                           /  |
             *                          2   3
             *                        /    /
             *                       5   7
             *                      /
             *                    11
             *                     \
             *                     13
             */
        }

        /**
         * 过滤树
         * @param tree
         * @param list
         * @return
         */
        private static Node filterTree(Node tree, List<Integer> list) {
            if(isRemoveNode(tree, list)){
                return null;
            }
            Iterator<Node> iterator = tree.getChildren().iterator();
            while (iterator.hasNext()){
                Node child = iterator.next();
                deleteNode(child, iterator, list);
            }
            return tree;
        }

        /**
         * 删除节点
         * @param child
         * @param iterator
         * @param list
         */
        private static void deleteNode(Node child, Iterator<Node> iterator, List<Integer> list) {
            if(isRemoveNode(child,list)){
                iterator.remove();
                return;
            }
            List<Node> childrenList = child.getChildren();
            if(CollectionUtils.isEmpty(childrenList)){
                return;
            }
            Iterator<Node> children = childrenList.iterator();
            while (children.hasNext()){
                Node childChild = children.next();
                deleteNode(childChild,children,list);
            }
        }

        /**
         * 判断该节点是否该删除
         * @param root
         * @param list  命中的节点
         * @return ture 需要删除  false 不能被删除
         */
        private static boolean isRemoveNode(Node root, List<Integer> list) {
            List<Node> children = root.getChildren();
            // 叶子节点
            if(CollectionUtils.isEmpty(children)){
                return !list.contains(root.getId());
            }
            // 子节点
            if(list.contains(root.getId())){
                return false;
            }
            // 如果存在一个子节点不能删除，那么就不能删除
            boolean bool = true;
            for (Node child : children) {
                if(!isRemoveNode(child,list)){
                    bool = false;
                    break;
                }
            }
            return bool;
        }

        /**
         * 初始化树状结构
         *                              1
         *                           /  |  \
         *                          2   3   4
         *                        / \   /\
         *                       5  6  7  8
         *                      /     /\
         *                    11     9 10
         *                   / \
         *                 12  13
         */
        private static Node initNode() {
            Node root = new Node(1,-1);
            List<Node> rootChildren = new ArrayList<>();
            Node node2= new Node(2, 1);
            Node node3= new Node(3, 1);
            Node node4= new Node(4, 1);
            rootChildren.add(node2);
            rootChildren.add(node3);
            rootChildren.add(node4);
            root.setChildren(rootChildren);

            Node node5= new Node(5, 2);
            Node node11= new Node(11, 5);
            List<Node> node5Children = new ArrayList<>();
            node5Children.add(node11);
            node5.setChildren(node5Children);

            Node node12= new Node(12, 11);
            Node node13= new Node(13, 11);
            List<Node> node11Children = new ArrayList<>();
            node11Children.add(node12);
            node11Children.add(node13);
            node11.setChildren(node11Children);

            Node node6= new Node(6, 2);

            List<Node> node2Children = new ArrayList<>();
            node2Children.add(node5);
            node2Children.add(node6);
            node2.setChildren(node2Children);

            Node node7= new Node(7, 2);
            Node node8= new Node(8, 2);

            List<Node> node3Children = new ArrayList<>();
            node3Children.add(node7);
            node3Children.add(node8);
            node3.setChildren(node3Children);

            Node node9= new Node(9, 7);
            Node node10= new Node(10, 7);

            List<Node> node7Children = new ArrayList<>();
            node7Children.add(node9);
            node7Children.add(node10);
            node7.setChildren(node7Children);
            return root;
        }

}
